package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序
 */
public class Demo02 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr, 0 , arr.length-1);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    private static int[] sort(int[] arr, int start, int end) {
        // 在递归过程中，会传入只有一个元素的数组，也就是start和end相等，将不做排序处理
        if(start<end){
            // 定义比较的标准数
            int standard = arr[start];
            // 定义低位和高位的下标
            int low = start;
            int high = end;
            // 循环让对应下标的值和标准数对比，进行迁移
            while (low<high){
                // 先判断高位下标的数
                while (low<high && standard<=arr[high])
                    high--;
                // 将高位的值赋值给低位
                arr[low] = arr[high];

                // 再判断低位下标的数
                while (low<high && arr[low]<=standard)
                    low++;
                arr[high] = arr[low];
            }
            arr[low] = standard;
            // 将分割左边的数组，递归进行处理
            sort(arr, start, low);
            // 将分割右边的数组，递归进行处理
            sort(arr, low+1, end);
        }
        return arr;
    }

}
